package LeetCode;

import java.util.Arrays;
import java.util.HashMap;

public class No41 {
    public static void main(String[] args) {
        int[] nums = {-1,4,2,1,9,10};
        System.out.println(firstMissingPositive(nums));
    }

    public static int firstMissingPositive(int[] nums) {
        //置换法
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            while(n>0&&n<=nums.length&&n!=nums[n-1]){
                int temp = nums[n-1];
                nums[n-1] = n;
                nums[i] = temp;
                n=temp;
            }
        }
//        for (int i = 0; i < nums.length; i++) {
//            System.out.print(nums[i]+" ");
//        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=i+1) return i+1;
        }
        return nums.length+1;

        //标记法
//        int n = nums.length;
//        for (int i = 0; i < n; ++i) {
//            if (nums[i] <= 0) {
//                nums[i] = n + 1;
//            }
//        }
//        for (int i = 0; i < n; ++i) {
//            int num = Math.abs(nums[i]);
//            if (num <= n) {
//                nums[num - 1] = -Math.abs(nums[num - 1]);
//            }
//        }
//        for (int i = 0; i < n; ++i) {
//            if (nums[i] > 0) {
//                return i + 1;
//            }
//        }
//        return n + 1;

//        int left = 0,right=0;
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            right = Math.max(right,nums[i]);
//            left = Math.min(left,nums[i]);
//            map.put(nums[i],i);
//        }
//        //System.out.println(left);
//        //System.out.println(right);
//        if(left>1) return left-1;
//        for (int i = 1; i <=right; i++) {
//            if(!map.containsKey(i)) return i;
//        }
//        return right+1;
    }
}
